#pragma once
#include <iostream>
#include <cassert>
using namespace std;

template<class K, class T>
struct AvltreeNode {
    AvltreeNode<K, T>* _left;
    AvltreeNode<K, T>* _right;
    AvltreeNode<K, T>* _parent;
    pair<K, T> _kv;
    int _bt; // 平衡因子

    AvltreeNode(const pair<K, T>& t)
        : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(t), _bt(0) {}
};

template<class K, class T>
class Avltree {
public:
    typedef AvltreeNode<K, T> Node;

    bool Insert(const pair<K, T>& v) {
        // 插入节点的逻辑
        if (_root == nullptr) {
            _root = new Node(v);
            return true;
        }
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur) {
            if (cur->_kv.first > v.first) {
                parent = cur;
                cur = cur->_left;
            } else if (cur->_kv.first < v.first) {
                parent = cur;
                cur = cur->_right;
            } else {
                return false; // 不允许重复键
            }
        }
        cur = new Node(v);
        if (parent->_kv.first < v.first) {
            parent->_right = cur;
            cur->_parent = parent;
        } else {
            parent->_left = cur;
            cur->_parent = parent;
        }

        // 更新平衡因子
        while (parent) {
            if (parent->_left == cur) {
                parent->_bt--;
            } else {
                parent->_bt++;
            }
            if (parent->_bt == 0) {
                break; // 树仍然平衡
            } else if (parent->_bt == 1 || parent->_bt == -1) {
                cur = parent;
                parent = parent->_parent;
            } else if (parent->_bt == 2 || parent->_bt == -2) {
                // 需要旋转
                // 判断旋转方向
                if (parent->_bt == 2 && cur->_bt == 1) { // 右边高，左单旋
                    // RotateL(parent); // 实现左单旋
                } else if (parent->_bt == -2 && cur->_bt == -1) { // 左边高，右单旋
                    // RotateR(parent); // 实现右单旋
                } else if (parent->_bt == 2 && cur->_bt == -1) { // 右左双旋
                    // RotateRL(parent);
                } else if (parent->_bt == -2 && cur->_bt == 1) { // 左右双旋
                    // RotateLR(parent);
                }
                break; // 旋转后不需要继续更新
            } else {
                assert(false); // 出现错误
            }
        }
        return true;
    }

    // 删除左单旋的实现
    void RotateL(Node* parent) { 
        Node* parent_parent = parent->_parent;
        Node* subR = parent->_right;//平衡因子为2的右子节点
        Node* subRL = subR->_left;//右子节点的左子点
        parent->_right = subRL;
        if(subRL)
            subRL->_parent = parent;
        subR->_left = parent;

        if(_root == parent)
        {
            _root = subR;
            subR->_parent = nullptr;
            return;
        }
        //需要更新平衡因子的节点不是根节点
        if(parent_parent->_left == parent)
        {
            parent_parent->_left = subR;
        }
        else
        {
            parent_parent->_right = subR;
        }
        parent->_parent = subR;
        subR->_parent = parent_parent;
        //最后更新平衡因子
        parent->_bt = 0;
        subR->_bt = 0;
    }//左单旋的步骤就是将平衡因子为2的节点的右子节点找到（subR）以及subR的左子节点（subRL，这个节点可能为空，需要进行判断），然后就是将parent节点作为subR的左节点，将subRL作为
    //parent的左节点，然后更新_parent节点的指向即可，最后再去更新平衡因子

    // 删除右单旋的实现
    void RotateR(Node* parent) {
        Node* parent_parent = parent->_parent;
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if(subLR)
            subLR->_parent = parent;
        subL->_right = parent;
        parent->_parent = subL;
        if(parent == _root)
        {
            _root = parent;
            subL->_parent = nullptr;
        }
        if(parent_parent->_left == parent)
        {
            parent_parent->_left = subL;
        }
        else
        {
            parent_parent->_right = subL;
        }
        //更新平衡因子
        parent->_bt = 0;
        subL->_bt = 0;
    }//左边高右单旋

    // 双旋转的函数
    void RotateRL(Node* parent) {
        Node* SubR = parent->_right;
        Node* SubrL = SubR->_left;
        int count = SubrL->_bt;
        RotateR(SubR);
        RotateL(parent);
        if (count == 0) {
            parent->_bt = SubR->_bt = SubrL->_bt = 0;
        } else if (count == 1) {
            SubR->_bt = SubrL->_bt = 0;
            parent->_bt = -1;
        } else if (count == -1) {
            SubR->_bt = 1;
            SubrL->_bt = parent->_bt = 0;
        } else {
            assert(false);
        }
    }

    void RotateLR(Node* parent) {
        Node* subL = parent->_left;
        Node* sublR = subL->_right;
        int count = sublR->_bt;
        RotateL(subL);
        RotateR(parent);
        if (count == 0) {
            parent->_bt = subL->_bt = sublR->_bt = 0;
        } else if (count == 1) {
            parent->_bt = sublR->_bt = 0;
            subL->_bt = -1;
        } else if (count == -1) {
            parent->_bt = 1;
            subL->_bt = sublR->_bt = 0;
        } else {
            assert(false);
        }
    }

    void Inorder() {
        _Inorder(_root);
    }

    bool isblance() {
        return _isblance(_root);
    }

private:
    bool _isblance(Node* root) {
        if (root == nullptr) {
            return true;
        }
        int lefthigh = Hight(root->_left);
        int righthigh = Hight(root->_right);
        if (righthigh - lefthigh != root->_bt) {
            cout << root->_kv.first << " 当前节点平衡因子异常" << endl;
            return false;
        }
        return abs(righthigh - lefthigh) < 2 && _isblance(root->_left) && _isblance(root->_right);
    }

    int Hight(Node* _root) {
        if (_root == nullptr) {
            return 0;
        }
        int lefthigh = Hight(_root->_left);
        int righthigh = Hight(_root->_right);
        return max(righthigh, lefthigh) + 1;
    }

    void _Inorder(Node* root) {
        if (root == nullptr) {
            return;
        }
        _Inorder(root->_left);
        cout << root->_kv.first << endl;
        _Inorder(root->_right);
    }

    Node* _root = nullptr;
};
